One or more embodiments of this invention relate generally to cryptographic proofs in data processing systems wherein a prover needs to prove to a verifier of the system that the prover satisfies a condition imposed by the verifier. Methods, apparatus and computer programs are provided for use in such systems and by provers and verifiers thereof.
There are numerous applications in which a proving entity (the “prover”) needs to prove certain information to a verifying entity (the “verifier”), where in general such an entity may comprise one or more individuals and/or devices interacting via some form of data processing system. For security or privacy-sensitive applications, cryptographic credentials are often employed in such proofs. A cryptographic credential is essentially a certificate generated via a cryptographic process by an issuing entity (the “issuer”) who has in some manner verified the information for which the credential is issued. This information is cryptographically encoded in the credential to certify the correctness of the information. The holder of a credential can then use the credential to make proofs to a verifier, via various cryptographic proof protocols, about the information encoded in the credential. In particular, cryptographic proofs can be made about the information encoded in the credential to demonstrate that the prover satisfies some condition imposed by the verifier. Such a condition typically relates to some requirement that the prover must satisfy in order to access a service, facility or other resource to which access is controlled by the verifier. Common applications include government or electronic ID cards which encode personal or other security-sensitive information about which proofs may need to be made for a variety of purposes. Here, a user might present his ID card to a terminal device of the verifier whereupon a processor on the card communicates with the terminal device to prove that some condition is satisfied, e.g. that the user's age as encoded in the credential is within a required range or that required information has been correctly disclosed to the verifier. There are also numerous applications involving access to resources via data communications networks such as the Internet. An exemplary system here might involve a user with a laptop, mobile phone, PDA (personal digital assistant) or other data processing device in communication with a remote server via the Internet, with verification of information via an appropriate cryptographic credential being required before the user is permitted access to a restricted web site.
Information can be encoded in cryptographic credentials in a variety of ways. In general, however, information to be certified by a credential is represented by some value or function which is then encoded in the credential via a cryptographic algorithm. The items of information certified by cryptographic credentials are referred to generally herein as “attributes”. Such an attribute can be any item of information attributed to a prover, relating, for example, to some property, quality, feature or other item belonging to, describing or otherwise associated with the prover. Cryptographic proof protocols then permit proofs to be made about encoded attributes. For privacy and security reasons, such proofs ideally keep the actual information disclosed to the verifier to a minimum. So-called “anonymous credentials”, for example, allow zero-knowledge (ZK) proofs to be made which do not reveal to a verifier any other information about prover attributes than that which is to be proved.
Cryptographic credentials, and in particular anonymous credential systems, offer powerful prover-centric control over disclosure of prover attributes. Consider the simple example of a user, carrying a credential on an ID card, who enters an age-restricted zone like a night-club and uses his anonymous credential at an entry terminal to prove an inequality over his age (e.g. “I am 21 or older”), without revealing his actual date of birth. The user reveals only the information necessary to satisfy the entry condition, and the anonymity set of the user is the set of all people holding credentials who are at least 21 years of age. However, this simple scenario reveals a difficulty with credential systems generally. That is, the entry terminal cannot verify that the ID card, and hence the credential used in the proof of age, actually belongs to the holder.
The particular problem of identity authentication forms the basis of biometrics. Biometrics provides techniques for recognizing individuals based on distinguishing physical or behavioural traits. Briefly, biometry for authentication consists of two main phases: enrollment and authentication. During enrollment, a series of measurements is made during which a physical or behavioural property (biometric) of the prover is measured repeatedly. These measurements are then processed to derive a biometric template. This template is characteristic of the prover on whom the measurements were made and is essentially a mathematical expression approximating what makes the prover distinct from other individuals. In the second, authentication phase, the prover reveals his template to the verifier along with some authority's signature on the template. The prover then exposes his relevant physical or behavioural biometric to a measurement device trusted only by the verifier. The verifier compares the resulting biometric measurement (the “observation”), after appropriate processing, with the prover's template. If the new biometric measurement matches the template (according to some predetermined matching criterion, typically that a calculated difference between the measurement and template does not exceed a threshold value), then the prover is judged to be the same individual and the identity authentication succeeds.
A problem with the basic biometric technique just described is that the template is quite sensitive private information. After all, it is the template which approximates as closely as possible a unique characterization of the prover's physical or behavioural qualities. A number of techniques have been proposed to address this fundamental problem with biometric authentication. One technique, known as “fuzzy matching”, involves the transformation of the prover's biometric template with a one-way function such that only the output of this function is disclosed to the verifier. A similar function is applied to the new biometric measurement made by the verifier to transform the measurement for comparison with the transformed template.
Another proposed solution to the above problem is usually called “match on chip” or “match on card”. With this system the prover provides a biometric, typically a fingerprint, directly to a trusted prover device such as a specially-constructed identity card or PDA-like device which carries the prover's biometric template. Since this hardware is trusted by both prover and verifier, and since this trusted device alone is exposed to the biometric information, this suffices for an authentication without revealing any prover information to the verifier. While this is an excellent solution for many circumstances, the need for special biometric hardware which, along with its cryptographic functionality, is trusted by both prover and verifier has both practical and cost implications inhibiting widespread application.
Another technique to address privacy in biometric authentication is described in “Privacy-preserving Similarity Evaluation and Application to Remote Biometrics Authentication”, Kikuchi et al., MDAI 2008, LNAI 5285, pp. 3-14, 2008. In this system, a user registers his biometric template in encoded form with an authentication server. The user inputs a new biometric measurement to a hardware device trusted by both prover and verifier. The hardware device then communicates with the authentication server to make a zero-knowledge proof that the new measurement matches the registered template without revealing the new measurement to the server.